You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have a security system connected, and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.
Example 1:
Input: nums = [2,3,2] Output: 3 Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2), because they are adjacent houses.
Example 2:
Input: nums = [1,2,3,1] Output: 4 Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3). Total amount you can rob = 1 + 3 = 4.
Example 3:
Input: nums = [0] Output: 0
Constraints:
1 <= nums.length <= 1000 <= nums[i] <= 1000
Average Rating: 4.17 (36 votes)
Solution
This problem is a minor extension to the original House Robber Problem. The only difference is that the first and the last houses are adjacent to each other and therefore, if the thief has robbed the first house, they cannot steal the last house and vice versa. As Hint 1 in the question suggests, "the problem becomes to rob either House[1]-House[n-1] or House[2]-House[n], depending on which choice offers more money. Now the problem has degenerated to the House Robber".
Approach 1: Dynamic Programming
Intuition
Assume we have nums of [7,4,1,9,3,8,6,5] as shown in the figure.
Since the start house and last house are adjacent to each other, if the thief decides to rob the start house 7, they cannot rob the last house 5. Similarly, if they select last house 5, they have to start from a house with value 4. Therefore, the final solution that we are looking for is to take the maximum value the thief can rob between houses of list [7,4,1,9,3,8,6] and [4,1,9,3,8,6,5]. For each of the lists, all we need to do is to figure the maximum value the thief can get using the approach in the original House Robber Problem.
Solving Original House Robber Problem with Dynamic Programming
Trivial cases:
- If there is one house, the answer is the value of that house.
- If there are two houses, the answer is
max(house1, house2). - If there are three houses, you can either pick the middle house or the sum of the first and the last house. Therefore, it boils down to
max(house3 + house1, house2).
To make the example more illustrative, imagine two thieves (t1 and t2) coordinating a grand robbery. They are equipped with walkie-talkies to communicate the values of houses to each other.
-
Before entering any of the houses, both
t1andt2have values of zero. -
t1, enters the first house and record the value of the house. If that is the only house to rob, they can rob this house and be done with it. -
If there is more than one house,
t1will leave a note of maximum value reaped until this point (which is just the value of the first house) and move to the next house whilet2moves into the houset1was in. Now,t1andt2are going to communicate over the walkie-talkie to ask who has the most value. At this point,t2will read the note left byt1when the values are compared. If they have only two houses to rob, they would rob the house with the most value and be done with it. -
If there are three houses,
t1will leave a note of the maximum value reaped until this point and move to the next house. Thent1will compare the value of the sum of the current house and the house whicht2is in with the value of the houset1was in. The maximum value between those two will be chosen andt2will move into the house next to it. -
If there are four houses,
t1will leave a note of the maximum value reaped until this point and move to the next house. Thent1will compare the value of the sum of the current house and the house whicht2is in with the value of the houset1was in. The maximum value between those two will be chosen andt2will move into the house next to it. -
This procedure is done over and over again as long as there are houses in
nums. Ift1has reached to the end ofnums,t1should have reaped the maximum amount obtainable from houses innums.
Implementation
Complexity Analysis
-
Time complexity : O(N) where N is the size of
nums. We are accumulating results as we are scanningnums. -
Space complexity : O(1) since we are not consuming additional space other than variables for two previous results and a temporary variable to hold one of the previous results.
October 15, 2020 8:48 AM
The hint on the problem says it all
If there are three houses, you can either pick the middle house or the sum of the first and the last house. Therefore, it boils down to max(house3 + house1, house2).
isn't house 3 and house 1 adjacent to each other? in case of three houses, shouldn't we pick the highest of the three houses?
Space complexity for the Python solution should be O(N) since list slicing creates a new list, in both cases of length N-1.
It could be done in one loop, not in two.
If there are only two houses, shouldn't we get 0 since we cannot rob adjacent houses?
Last Edit: October 7, 2020 2:05 AM
Slicing is still a shallow copy. Therefore, space is O(1)
Can anyone please help to understand this question? if i have a linear list [1, 3, 4].My understanding you can only rob( house1 + house4) and not house3 +( house1 + house4).Since house is at the middle of both 1 and 4
Last Edit: June 6, 2021 8:37 PM
The variable names are so bad in most leetcode solutions..
April 23, 2021 9:19 PM
Space complexity is incorrect as of 23-Apr-21. It should be O(N) because slicing the list creates a copy. It is possible to achieve O(1) by rewriting rob_simple to accept start and end indexes.
Time Submitted | Status | Runtime | Memory | Language |
|---|---|---|---|---|
| 05/31/2021 08:44 | Accepted | 0 ms | 7.7 MB | cpp |
| 06/08/2020 13:36 | Accepted | 8 ms | 7.8 MB | cpp |
| 06/08/2020 13:35 | Runtime Error | N/A | N/A | cpp |
| 06/08/2020 13:34 | Runtime Error | N/A | N/A | cpp |
| 06/08/2020 13:33 | Wrong Answer | N/A | N/A | cpp |
xxxxxxxxxxclass Solution {public: int rob(vector<int>& nums) { if(nums.size() == 1) return nums[0]; if(nums.size() == 2) return max(nums[0], nums[1]); return max(robHelp(nums, 0, nums.size()-1), robHelp(nums, 1, nums.size())); } int robHelp(vector<int>& nums, int start, int end) { int a = 0, b = 0, res = 0; for(int i=start;i<end;i++) { res = max(a, b + nums[i]); b = a; a = res; } return res; }};